/**
 * @author hewei
 * @version 1.0
 * @description: 1043. 分隔数组以得到最大和
 * @date 2022/10/18 15:45
 */

public class MaxSumAfterPartitioning {

    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            int max = arr[i - 1];
            for (int j = i; j >= 1 && i - j + 1 <= k; j--) {
                max = Math.max(max, arr[j - 1]);
                dp[i] = Math.max(dp[i], dp[j - 1] + max * (i - j + 1));
            }
        }
        return dp[n];
    }
}
